{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Subarray Sum with One Deletion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除一次得到子数组最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组，返回它的某个&nbsp;<strong>非空</strong> 子数组（连续元素）在执行一次可选的删除操作后，所能得到的最大元素总和。换句话说，你可以从原数组中选出一个子数组，并可以决定要不要从中删除一个元素（只能删一次哦），（删除后）子数组中至少应当有一个元素，然后该子数组（剩下）的元素总和是所有子数组之中最大的。</p>\n",
    "\n",
    "<p>注意，删除一个元素后，子数组 <strong>不能为空</strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,-2,0,3]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>我们可以选出 [1, -2, 0, 3]，然后删掉 -2，这样得到 [1, 0, 3]，和最大。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,-2,-2,3]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们直接选出 [3]，这就是最大和。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [-1,-1,-1,-1]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>最后得到的子数组不能为空，所以我们不能选择 [-1] 并从中删去 -1 来得到 0。\n",
    "     我们应该直接选择 [-1]，或者选择 [-1, -1] 再从中删去一个 -1。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "<meta charset=\"UTF-8\" />\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= arr[i] &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-subarray-sum-with-one-deletion](https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-subarray-sum-with-one-deletion](https://leetcode.cn/problems/maximum-subarray-sum-with-one-deletion/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,-2,0,3]', '[1,-2,-2,3]', '[-1,-1,-1,-1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        res=dp0=dp1=arr[0]\n",
    "        \n",
    "        for i in range(1,len(arr)):\n",
    "            dp1=max(dp1+arr[i],dp0)\n",
    "            dp0=max(dp0+arr[i],arr[i])\n",
    "            res=max(res,dp0,dp1)\n",
    "\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        if not arr:\n",
    "            return 0\n",
    "        dp0, dp1, s, re = arr[0], 0, arr[0] if arr[0] > 0 else 0, arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            s += arr[i]\n",
    "            dp1 = max(dp0, dp1+arr[i])\n",
    "            dp0 = s\n",
    "            re = max(re, dp0, dp1)\n",
    "            if s < 0:\n",
    "                s = 0\n",
    "        return re\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = arr[0]\n",
    "        suf_no_del = arr[0]  # 不删除能得到的最大元素和\n",
    "        suf_del = 0  # 删除一个元素后能得到的最大元素和\n",
    "        for i in range(1, n):\n",
    "            # 如果删除一个元素，有2种情况：\n",
    "            # 1）之前已经删除过了，这里不再删除，所以是suf_del + arr[i]\n",
    "            # 2）之前没有删除，这里进行删除，所以是suf_no_del\n",
    "            suf_del = max(suf_del + arr[i], suf_no_del)\n",
    "            # 如果不删除元素：之前没有删除，这里也不删除\n",
    "            # 1）如果前缀和 suf_no_del > 0的话，a[i]加上它才能得到一个更大的和\n",
    "            # 2）否则，没必要加上前缀和，直接从自身开始重新累加\n",
    "            suf_no_del = max(suf_no_del + arr[i], arr[i])\n",
    "            res = max(res, suf_del, suf_no_del)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        cur hasdel\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        ok = False\n",
    "        for i in arr:\n",
    "            if i >=0:\n",
    "                ok = True\n",
    "                break\n",
    "        if ok is False:\n",
    "            return max(arr)\n",
    "        dp = {}\n",
    "        m1= 0\n",
    "        a,b= 0,0\n",
    "        for k,v in enumerate(arr):\n",
    "            if k == 0:\n",
    "                a = v\n",
    "                b = 0\n",
    "                m1 = max(m1, v)\n",
    "            else:\n",
    "                if v >=0:\n",
    "                    a = max(v, v+ a)\n",
    "                    b = max(v, v+ b)\n",
    "                    m1 = max(m1, a, b )\n",
    "                else:\n",
    "                    b = max(b+v, a)\n",
    "                    a = v + a\n",
    "                    m1 = max(m1, a, b)\n",
    "        return m1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        a, b = arr[0], 0\n",
    "        ans = max(arr)\n",
    "        for x in arr[1:]:\n",
    "            b = max(a, b+x)\n",
    "            a = max(a+x, x)\n",
    "            ans = max(ans, a, b)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: list[int]) -> int:\n",
    "        dp0 = arr[0]\n",
    "        dp1 = 0\n",
    "        res = dp0\n",
    "        for i in range(1, len(arr)):\n",
    "            dp1 = max(dp1 + arr[i], dp0)\n",
    "            dp0 = max(dp0, 0) + arr[i]\n",
    "            res = max(res, dp0, dp1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        ret = dp0 = dp1 = -inf\n",
    "        for x in arr:\n",
    "            dp1 = max(dp1 + x, dp0)\n",
    "            dp0 = max(dp0, 0) + x\n",
    "            ret = max(ret, dp0, dp1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        f = [-1e9] * (n + 1)  # 以 arr[i] 开头的子数组最大和\n",
    "        res = float('-inf')\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            f[i] = max(f[i + 1], 0) + arr[i]\n",
    "            res = max(res, f[i])\n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            res = max(res, s + f[i + 1])  # 删除 arr[i] 的区间最大和\n",
    "            s = max(0, s) + arr[i]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        l1 = []\n",
    "        ts = 0\n",
    "        l = 0\n",
    "        m1 = []\n",
    "        m2 = []\n",
    "        MIN = 0\n",
    "        id = []\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i]<0:\n",
    "                m2.append(arr[i])\n",
    "            if arr[i] * ts >= 0:\n",
    "                ts += arr[i]\n",
    "                l += 1\n",
    "                if arr[i] < MIN:\n",
    "                    MIN = arr[i]\n",
    "            elif arr[i] * ts < 0:\n",
    "                id.append(i)\n",
    "                if l > 0 and ts != 0:\n",
    "                    l1.append(ts)\n",
    "                    ts = arr[i]\n",
    "                    l = 1\n",
    "                    m1.append(MIN)\n",
    "                    MIN = 0\n",
    "                    if arr[i] < 0:\n",
    "                        MIN = arr[i]\n",
    "\n",
    "        if l > 0 and ts != 0:\n",
    "            l1.append(ts)\n",
    "            m1.append(MIN)\n",
    "        MAX = 0\n",
    "        for i in range(len(l1)):\n",
    "            MIN = 0\n",
    "            if l1[i] > 0:\n",
    "                s = l1[i]\n",
    "                if s > MAX:\n",
    "                    MAX = s\n",
    "                for j in range(i + 1, len(l1)):\n",
    "                    s += l1[j]\n",
    "                    if m1[j] < 0:\n",
    "                        if MIN > m1[j]:\n",
    "                            MIN = m1[j]\n",
    "                    else:\n",
    "                        if s - MIN > MAX:\n",
    "                            MAX = s - MIN\n",
    "                        elif s - MIN<=0:\n",
    "                            break\n",
    "        if MAX == 0:\n",
    "            if len(m2)>0:\n",
    "                return max(m2)\n",
    "            else:\n",
    "                return 0\n",
    "        return MAX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        f = [0] * (n +1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            f[i] = f[i-1] + arr[i-1] \n",
    "        \n",
    "        lmin = [0] * (n+1)\n",
    "        rmax = [0] * (n+1)\n",
    "\n",
    "        rmax[n] = float('-inf')\n",
    "        for i in range(n-1, -1, -1):\n",
    "            rmax[i] = max(rmax[i+1], f[i+1]) \n",
    "        \n",
    "        lmin[0] = float('inf')\n",
    "        for i in range(1, n+1):\n",
    "            lmin[i] = min(lmin[i-1], f[i-1]) \n",
    "        \n",
    "        ans = float('-inf') \n",
    "        for i in range(1, n+1):\n",
    "            if arr[i-1] < 0:\n",
    "                ans = max(ans, rmax[i] - lmin[i] - arr[i-1])\n",
    "            else:\n",
    "                ans = max(ans, rmax[i] - lmin[i])\n",
    "            ans = max(ans ,arr[i-1])\n",
    "        \n",
    "        return ans  \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "\n",
    "        arr_len = len(arr)\n",
    "\n",
    "        pos_acc_list = [arr[0]]\n",
    "    \n",
    "        for i in range(1,arr_len):\n",
    "            \n",
    "            if arr[i] < 0 or pos_acc_list[-1]< 0:\n",
    "                    \n",
    "                pos_acc_list.append(arr[i])\n",
    "            else :\n",
    "                \n",
    "                pos_acc_list[-1] += arr[i]\n",
    "\n",
    "        arr = pos_acc_list\n",
    "        \n",
    "        arr_len = len(arr)\n",
    "\n",
    "        dp = [[-math.inf for i in range(arr_len)] for j in range(2) ]\n",
    "        \n",
    "        max_result = dp[0][0] = arr[0]\n",
    "        \n",
    "        dp[1][0] = 0\n",
    "        \n",
    "        for i in range(1,arr_len):\n",
    "            \n",
    "            dp[0][i] = max(arr[i],dp[0][i-1]+arr[i])\n",
    "            \n",
    "            dp[1][i] = max(dp[1][i-1]+arr[i] ,dp[0][i-1] , dp[0][i-1]+arr[i] )\n",
    "            \n",
    "            max_result = max(max_result,dp[0][i],dp[1][i]) \n",
    "        \n",
    "        return max_result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        ret = dp0 = dp1 = -inf\n",
    "        for x in arr:\n",
    "            dp1 = max(dp1 + x, dp0)\n",
    "            dp0 = max(dp0, 0) + x\n",
    "            ret = max(ret, dp0, dp1)\n",
    "        return ret\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre, beh = [0] * n, [0] * n\n",
    "        pre[0] = arr[0]\n",
    "        beh[-1] = arr[-1]\n",
    "        for i in range(1, n):\n",
    "            pre[i] = max(pre[i-1] + arr[i], arr[i])\n",
    "            beh[-1-i] = max(beh[-i] + arr[-1-i], arr[-1-i])\n",
    "        ret = max(pre)\n",
    "        for i in range(1, n-1):\n",
    "            ret = max(ret, pre[i-1] + beh[i+1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        if n==1:\n",
    "            return arr[0]\n",
    "        dp1=[0]*n\n",
    "        dp2=[0]*n\n",
    "        dp1[0]=arr[0]\n",
    "        for i in range(1,n):\n",
    "\n",
    "            dp1[i]=max(dp1[i-1]+arr[i],arr[i])\n",
    "            dp2[i]=max(dp2[i-1]+arr[i],dp1[i-1])\n",
    "        return max( max(dp1),max(dp2[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dpkeep = [0] * n\n",
    "        dpremove = [0] * n\n",
    "        dpkeep[0] = arr[0]\n",
    "        dpremove[0] = -float('inf')\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            dpkeep[i] = max(dpkeep[i-1] + arr[i], arr[i])\n",
    "            dpremove[i] = max(\n",
    "                dpkeep[i-1],  # 删除i，\n",
    "                dpremove[i-1] + arr[i],  # 保留i\n",
    "                )\n",
    "        return max(dpremove + dpkeep)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        debug = 0\n",
    "        L = -10**5\n",
    "        maxone = L\n",
    "        left = [0]\n",
    "        right = [0]\n",
    "        minleft = [0]\n",
    "        minright = [0]\n",
    "        for i in range(n):\n",
    "            left.append(left[-1]+arr[i])\n",
    "            right.append(right[-1]+arr[n-1-i])\n",
    "            maxone = max(maxone, left[-1])\n",
    "            maxone = max(maxone, right[-1])\n",
    "            maxone = max(maxone, left[-1]-left[minleft[-1]])\n",
    "            maxone = max(maxone, right[-1]-right[minright[-1]])\n",
    "            minleft.append(minleft[-1] if left[minleft[-1]] < left[-1] else i+1)\n",
    "            minright.append(minright[-1] if right[minright[-1]] < right[-1] else i+1)\n",
    "        if debug:\n",
    "            print(left,minleft)\n",
    "            print(right,minright)\n",
    "            print(maxone)\n",
    "        for i in range(n):\n",
    "            now = 0\n",
    "            if i:\n",
    "                now += left[i]-left[minleft[i-1]]\n",
    "            if n-1-i:\n",
    "                now += right[n-1-i]-right[minright[n-i-2]]\n",
    "            if debug:\n",
    "                print(i,arr[i],now)\n",
    "            if i or n-1-i:\n",
    "                maxone = max(maxone,now)\n",
    "        return maxone\n",
    "'''\n",
    "[1,-2,0,3]\n",
    "[1,-2,-2,3]\n",
    "[-1,-1,-1,-1]\n",
    "[-8,7,-12,-1,0,11,-2,-3,4,-13,2,3,-6]\n",
    "[8,-1,6,-7,-4,5,-4,7,-6]\n",
    "[-23,20,19,22,-3,-24,23,-22,1,12,11,-18,21,16,15,-14,-7,20,19,-10,-19,8,-9,-6]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # pre_sum = [0 for i in range(len(arr)+1)]\n",
    "        # back_sum = [0 for i in range(len(arr)+1)]\n",
    "        nums =arr\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return arr[0]\n",
    "        # if n==2:\n",
    "\n",
    "        # for i in range(1,n+1):\n",
    "        #     pre_sum[i] = nums[i-1]+pre_sum[i-1]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     back_sum[i] = back_sum[i-1]+nums[i-1]\n",
    "        dp_l2r = [0 for i in range(n)]\n",
    "        dp_r2l = [0 for i in range(n)]\n",
    "        dp_l2r[0] = nums[0]\n",
    "        dp_r2l[n-1] = nums[n-1]\n",
    "        res = [0 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dp_l2r[i] = max(dp_l2r[i-1]+nums[i],nums[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            dp_r2l[i] = max(dp_r2l[i+1]+nums[i],nums[i])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                res[0] = dp_r2l[1]\n",
    "                continue\n",
    "            if i==n-1:\n",
    "                res[n-1] = dp_l2r[n-2]\n",
    "                continue\n",
    "            res[i] = max([dp_l2r[i-1],dp_r2l[i+1],dp_l2r[i-1]+dp_r2l[i+1]])\n",
    "        return max(max(res),max(dp_l2r))\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # pre_sum = [0 for i in range(len(arr)+1)]\n",
    "        # back_sum = [0 for i in range(len(arr)+1)]\n",
    "        nums =arr\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return arr[0]\n",
    "        # if n==2:\n",
    "\n",
    "        # for i in range(1,n+1):\n",
    "        #     pre_sum[i] = nums[i-1]+pre_sum[i-1]\n",
    "        # for i in range(n-2,-1,-1):\n",
    "        #     back_sum[i] = back_sum[i-1]+nums[i-1]\n",
    "        dp_l2r = [0 for i in range(n)]\n",
    "        dp_r2l = [0 for i in range(n)]\n",
    "        dp_l2r[0] = nums[0]\n",
    "        dp_r2l[n-1] = nums[n-1]\n",
    "        res = [0 for i in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dp_l2r[i] = max(dp_l2r[i-1]+nums[i],nums[i])\n",
    "        for i in range(n-2,-1,-1):\n",
    "            dp_r2l[i] = max(dp_r2l[i+1]+nums[i],nums[i])\n",
    "        \n",
    "        for i in range(n):\n",
    "            if i==0:\n",
    "                res[0] = dp_r2l[1]\n",
    "                continue\n",
    "            if i==n-1:\n",
    "                res[n-1] = dp_l2r[n-2]\n",
    "                continue\n",
    "            res[i] = max([dp_l2r[i-1],dp_r2l[i+1],dp_l2r[i-1]+dp_r2l[i+1]])\n",
    "        return max(max(res),max(dp_l2r))\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        cache = [[-inf] * len(arr) for i in range(0,2)]\n",
    "        def dp(i: int, j: int) -> int:\n",
    "            if i < 0:\n",
    "                return -inf\n",
    "            if cache[j][i] != -inf:\n",
    "                return cache[j][i]\n",
    "            \n",
    "            if j == 0: \n",
    "                cache[j][i] = max(dp(i - 1, 0), 0) + arr[i]\n",
    "            else:\n",
    "                cache[j][i] = max(dp(i - 1, 0), dp(i - 1, 1) + arr[i])\n",
    "            return cache[j][i]\n",
    "        return max(max(dp(i, 0), dp(i, 1)) for i in range(len(arr)))\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0]*2 for _ in range(n)]\n",
    "        dp[0][0] = arr[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i][0] = max(dp[i-1][0] + arr[i], arr[i]) #不删\n",
    "            dp[i][1] = max(dp[i-1][1] + arr[i], dp[i-1][0])\n",
    "        \n",
    "        ans = -inf\n",
    "        for i in range(n):\n",
    "            for j in range(2):\n",
    "                if i == 0 and j == 1:\n",
    "                    continue\n",
    "                ans = max(ans, dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 前缀和\n",
    "        def maxSubArray(nums: List[int]) -> int:\n",
    "            pre = min_pre = 0\n",
    "            ret = -inf\n",
    "            for x in nums:\n",
    "                pre += x\n",
    "                ret = max(ret, pre - min_pre)\n",
    "                min_pre = min(min_pre, pre)\n",
    "            return ret\n",
    "        ret = -inf\n",
    "        for i in range(1, len(arr)-1):\n",
    "            ret = max(ret, maxSubArray(arr[:i] + arr[i+1:]))\n",
    "        return max(ret, maxSubArray(arr))\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = [[0] * 2 for _ in range(n+1)]\n",
    "        dp[0] = [-inf] * 2\n",
    "        for i in range(n):\n",
    "            dp[i+1][0] = max(dp[i][0], 0) + arr[i]\n",
    "            dp[i+1][1] = max(dp[i][1] + arr[i], dp[i][0])\n",
    "        return max(max(x) for x in dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: [int]) -> int:\n",
    "        dp = [[0 for _ in range(2)] for _ in range(len(arr))]\n",
    "        dp[0][0] = arr[0]\n",
    "        res = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            dp[i][0] = max(dp[i - 1][0], 0) + arr[i]\n",
    "            dp[i][1] = max(dp[i - 1][1] + arr[i], dp[i - 1][0])\n",
    "            res = max(res, dp[i][0], dp[i][1])\n",
    "            pass\n",
    "        return res\n",
    "\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        dp_max = [ [0, 0 ,0] for _ in arr ]   #  dp_max[idx][included]\n",
    "        dp_max[0][0] = arr[0]\n",
    "        dp_max[0][1] = -inf    #不可取到\n",
    "        dp_max[0][2] = -inf    #不可取到\n",
    "        dp_min = arr[0]\n",
    "        idx = 1\n",
    "        res = dp_max[0][0]\n",
    "        for num in arr[1:]:\n",
    "            dp_max[idx][0] = max(dp_max[idx-1][0] + num , num)\n",
    "            dp_max[idx][1] = max( dp_max[idx-1][0] + num - dp_min , dp_max[idx-1][1] + num ,dp_max[idx-1][2] + num)\n",
    "            dp_max[idx][2] = dp_max[idx-1][0]\n",
    "            if dp_max[idx-1][0] >= 0 :\n",
    "                dp_max[idx][0] = dp_max[idx-1][0] + num\n",
    "                dp_min =  min( num , dp_min )\n",
    "            else:\n",
    "                dp_max[idx][0] = num\n",
    "                dp_min = num\n",
    "            res = max( res , max( dp_max[idx] ) )\n",
    "            idx += 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1: return arr[0]\n",
    "        ret = [-inf for _ in range(n)]\n",
    "\n",
    "        f = [[-inf, -inf] for _ in range(n)]\n",
    "        f[0][0] = arr[0]\n",
    "        f[0][1] = arr[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            f[i][0] = max(f[i-1][0] + arr[i], arr[i])\n",
    "            f[i][1] = max(f[i-1][0], f[i-1][1] + arr[i], arr[i])\n",
    "\n",
    "            ret[i] = max(ret[i-1], f[i][0], f[i][1])\n",
    "\n",
    "        # print(ret)\n",
    "        return ret[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        import numpy as np\n",
    "        res = arr[0]\n",
    "        dp = np.zeros((len(arr), 2), dtype=int)\n",
    "        dp[0][0] = arr[0]\n",
    "        for idx, num in enumerate(arr):\n",
    "            if idx == 0:\n",
    "                continue\n",
    "            dp[idx][0] = max(dp[idx - 1][0], 0) + num\n",
    "            dp[idx][1] = max(dp[idx - 1][0], dp[idx - 1][1] + num)\n",
    "            res = max(res, max(dp[idx][0], dp[idx][1]))\n",
    "        return int(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "import numpy as np\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        因为题目中讲是连续的，所以我们可以讲所有的正数/负数合并起来，并且记录每段的最大的正数和负数\n",
    "        得到arr1，like [1, -1, 1, -1, 1]\n",
    "        然后我们再针对arr1进行贪心的算法\n",
    "        sum = 0\n",
    "        sum += arr1[I]\n",
    "        if sum < 0:\n",
    "            说明此时已经是负数了，需要重新开始计算\n",
    "            我们选择上一段正数和，然后再加上abs(最大的负数)，记录该值，然后取最大返回\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        if len(arr) == 1:\n",
    "            return arr[0]\n",
    "        arr1 = [arr[0]]\n",
    "        min_values = [arr[0]]\n",
    "        max_values = [arr[0]]\n",
    "        for idx in range(1, len(arr)):\n",
    "            if arr1[-1] * arr[idx] >= 0:\n",
    "                arr1[-1] += arr[idx]\n",
    "                min_values[-1] = min(min_values[-1], arr[idx])\n",
    "                max_values[-1] = max(max_values[-1], arr[idx])\n",
    "            else:\n",
    "                arr1.append(arr[idx])\n",
    "                max_values.append(arr[idx])\n",
    "                min_values.append(arr[idx])\n",
    "        if len(arr1) == 1:\n",
    "            return arr1[0] if arr1[0] >= 0 else max_values[0]\n",
    "        # if arr1[0] <= 0:\n",
    "        #     arr1 = arr1[1:]\n",
    "        #     max_values = max_values[1:]\n",
    "        #     min_values = min_values[1:]\n",
    "        # if arr1[-1] <= 0:\n",
    "        #     arr1 = arr1[:-1]\n",
    "        #     min_values = min_values[:-1]\n",
    "        #     max_values = max_values[:-1]\n",
    "\n",
    "        def __core(cur_arr, cur_min_values):\n",
    "            res = 0\n",
    "            cur_idx = 0\n",
    "            last_idx = -1\n",
    "            while cur_idx < len(cur_arr):\n",
    "                tmp = cur_idx\n",
    "                cur_sum = 0\n",
    "                cur_min_value = np.inf\n",
    "                # 记录删除的位置\n",
    "                delete_pos = -1\n",
    "                for idx in range(tmp, len(cur_arr)):\n",
    "                    cur_sum += cur_arr[idx]\n",
    "                    cur_idx = idx + 1\n",
    "                    if cur_sum >= 0:\n",
    "                        # 尚不用删除\n",
    "                        if delete_pos == -1:\n",
    "                            cur_min_value = min(cur_min_value, cur_min_values[idx])\n",
    "                            res = max(res, cur_sum, cur_sum - cur_min_value)\n",
    "                        else:\n",
    "                            res = max(res, cur_sum)\n",
    "                        continue\n",
    "                    else:\n",
    "                        if delete_pos != -1:\n",
    "                            cur_idx = last_idx\n",
    "                            break\n",
    "                        if delete_pos == -1 and (cur_sum - cur_min_values[idx]) > 0:\n",
    "                            # 还有救，可以继续\n",
    "                            delete_pos = cur_idx\n",
    "                            cur_sum = cur_sum - cur_min_values[idx]\n",
    "                        else:\n",
    "                            # 没救了，重新开始计数\n",
    "                            break\n",
    "                if delete_pos != -1:\n",
    "                    cur_idx = delete_pos\n",
    "            return res\n",
    "        res = __core(arr1, min_values)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        f=[[-float('inf'), -float('inf')]+[0,0] for _ in range(n+1)]\n",
    "        print(f)\n",
    "        for i in range(n):\n",
    "            f[i+1][0]=max(f[i][0],0)+arr[i]\n",
    "            f[i+1][1]=max(f[i][0], f[i][1]+arr[i])\n",
    "        ans=-float('inf')\n",
    "        for i in range(n+1):\n",
    "            ans=max(max(ans,f[i][0]), f[i][1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # dp[i][0]:连续子数组包含当前元素\n",
    "        # dp[i][1]:连续子数组不包含当前元素\n",
    "        if len(arr) == 1:return arr[0]\n",
    "        dp = [[float('-inf') for _ in range(2)] for _ in range(len(arr))]\n",
    "        dp_in = [float('-inf')] * len(arr)\n",
    "        dp_out = [float('-inf')] * len(arr)\n",
    "        dp_in[0] = arr[0]\n",
    "        dp_out[0] = 0\n",
    "        max_value = float('-inf')\n",
    "        for i in range(1, len(arr)):\n",
    "            dp_in[i] = max(dp_in[i-1]+arr[i], arr[i])\n",
    "            dp_out[i] = max(dp_in[i-1], dp_out[i-1]+arr[i])\n",
    "            max_value = max(dp_in[i], dp_out[i], max_value)\n",
    "        print(dp_in)\n",
    "        print(dp_out)\n",
    "        return max_value\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        dp1, dp2 = {}, {}\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return arr[0]\n",
    "\n",
    "        ans = -10001\n",
    "        dp1[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            dp1[i] = max(dp1[i-1], 0) + arr[i]\n",
    "            ans = max(ans, dp1[i])\n",
    "        \n",
    "        dp2[0] = None\n",
    "        dp2[1] = arr[1]\n",
    "        for i in range(2, n):\n",
    "            dp2[i] = max(dp2[i-1], dp1[i-2]) + arr[i]\n",
    "            ans = max(ans, dp2[i])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        presum = [0]\n",
    "        for i in arr:\n",
    "            if i <= 0:\n",
    "                if presum[-1] + i >= 0:\n",
    "                    presum.append(presum[-1] + i)\n",
    "                else:\n",
    "                    presum.append(0)\n",
    "            else:\n",
    "                if presum[-1] < 0:\n",
    "                    presum.append(i)\n",
    "                else:\n",
    "                    presum.append(presum[-1] + i)\n",
    "        @lru_cache(None)\n",
    "        def dp(i):\n",
    "            if i == 0:\n",
    "                return arr[0]\n",
    "            if i == 1:\n",
    "                return max(0,arr[0]) + arr[1]\n",
    "            return max(dp(i-1), presum[i-1]) + arr[i]\n",
    "        \n",
    "        ans = float('-inf')\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            temp = dp(i)\n",
    "            #print(i,temp)\n",
    "            ans = max(ans, temp)\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "      dp = [[[],[]] for i in arr]\n",
    "      dp[0][0] = arr[0]\n",
    "      dp[0][1] = arr[0]\n",
    "      i = 1\n",
    "      while i<len(arr):\n",
    "        dp[i][0] = max(dp[i-1][0]+arr[i],dp[i-1][1])\n",
    "        dp[i][1] = max(arr[i],dp[i-1][1]+arr[i])\n",
    "        i = i + 1\n",
    "      return max([i[0] for i in dp]+[i[1] for i in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        ps, cur = [], [0]*2\n",
    "        for i in range(len(arr)):\n",
    "            if cur[0] < 0:\n",
    "                cur = [0]*2\n",
    "            ps.append(tuple(cur))\n",
    "            cur[0] += arr[i]\n",
    "            cur[1] += 1\n",
    "        bs, cur = [], [0]*2\n",
    "        for i in range(len(arr)-1, -1, -1):\n",
    "            if cur[0] < 0:\n",
    "                cur = [0]*2\n",
    "            bs.append(tuple(cur))\n",
    "            cur[0] += arr[i]\n",
    "            cur[1] += 1\n",
    "        bs = bs[::-1]\n",
    "        ans = float('-inf')\n",
    "        for i in range(len(arr)):\n",
    "            if ps[i][1] == 0 and bs[i][1] == 0:\n",
    "                val = arr[i]\n",
    "            else:\n",
    "                val = ps[i][0]+bs[i][0]\n",
    "                if arr[i] > 0:\n",
    "                    val += arr[i]\n",
    "            ans = max(ans, val)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[[0]*n for i in range(2)]\n",
    "        dp[0][0]=arr[0]\n",
    "        dp[1][0]=0\n",
    "        if n==1:\n",
    "            return arr[0]\n",
    "        for i in range(1,n):\n",
    "            dp[0][i] = max(dp[0][i-1],0) +arr[i]\n",
    "            dp[1][i] = max(dp[0][i-1],dp[1][i-1]+arr[i])\n",
    "        dp[1][0]=arr[0]\n",
    "        print(dp)\n",
    "        return int(np.max(dp))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        cans = max(arr)\n",
    "        d,d1,rd = {},{},{}\n",
    "        d[-1]=0\n",
    "        d1[0]=max(0,arr[0])\n",
    "        d1[-1]=0\n",
    "        for i,n in enumerate(arr):\n",
    "            if i==0:\n",
    "                d[i]=n\n",
    "            else:\n",
    "                d[i]=max(n,n+d[i-1])\n",
    "                d1[i]=max(n,d[i],n+d[i-2],d[i-1])\n",
    "        cs = 0\n",
    "        while arr:\n",
    "            cs+=arr.pop()\n",
    "            rd[len(arr)]=cs\n",
    "            cs = max(cs,0)\n",
    "        #print(d,d1,rd,cans)\n",
    "        for p in rd:\n",
    "            #print(p)\n",
    "            cans = max(cans,d[p-1]+rd[p],rd[p]+d1[p-1])\n",
    "            #rint(cans,'a')\n",
    "        return cans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        dp = [[[float(\"-inf\"), float(\"-inf\")], [float(\"-inf\"), float(\"-inf\")]] for _ in range(len(arr)+1)]\n",
    "        for i in range(1, len(dp)):\n",
    "            dp[i][1][1] = max(dp[i-1][1][1]+arr[i-1], arr[i-1])\n",
    "            dp[i][0][1] = dp[i-1][1][1]\n",
    "            dp[i][1][0] = max(dp[i-1][0][1]+arr[i-1], dp[i-1][1][0]+arr[i-1])\n",
    "            dp[i][0][0] = max(dp[i][1][0], dp[i-1][0][0], dp[i][0][1], dp[i][1][1])\n",
    "        return dp[-1][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "\n",
    "        @cache\n",
    "        def zero_delete(index):\n",
    "            # arr[index] 结尾的 / 不做删除操作 / 最大和\n",
    "            if index == 0:\n",
    "                return arr[index]\n",
    "            r1 = arr[index]\n",
    "            r2 = zero_delete(index - 1) + arr[index]\n",
    "            return max(r1, r2)\n",
    "        \n",
    "        @cache\n",
    "        def one_delete(index):\n",
    "            # arr[index] 结尾的 / 做1删除操作 / 最大和\n",
    "            if index == 0:\n",
    "                return arr[index]\n",
    "            \n",
    "            r1 = zero_delete(index - 1)\n",
    "            r2 = one_delete(index - 1) + arr[index]\n",
    "            return max(r1, r2)\n",
    "        \n",
    "        ans = arr[0]\n",
    "        for i in range(len(arr)):\n",
    "            ans = max(ans, one_delete(i), zero_delete(i))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        cur hasdel\n",
    "        :param arr:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        ret = []\n",
    "        ok = False\n",
    "        for i in arr:\n",
    "            if i >=0:\n",
    "                ok = True\n",
    "                break\n",
    "        if ok is False:\n",
    "            return max(arr)\n",
    "        dp = {}\n",
    "        m1= 0\n",
    "        for k,v in enumerate(arr):\n",
    "            if k == 0:\n",
    "                if v >= 0:\n",
    "                    dp[(k,0)] = v\n",
    "                    dp[(k, 1)] = 0\n",
    "                    m1 = max(m1, v)\n",
    "                else:\n",
    "                    dp[(k,0)] = v\n",
    "                    dp[(k, 1)] = 0\n",
    "                    m1 = max(m1, v)\n",
    "            else:\n",
    "                if v >=0:\n",
    "                    res1 = max(v, v+ dp[(k-1,0)])\n",
    "                    res2 = max(v, v+ dp[(k-1,1)])\n",
    "                    dp[(k,0)] = res1\n",
    "                    dp[(k,1)] = res2\n",
    "                    m1 = max(m1, res1, res2 )\n",
    "                else:\n",
    "                    res1 = v + dp[(k-1,0)]\n",
    "                    res2 = max(dp[(k-1,1)]+v , dp[(k-1,0)] )\n",
    "                    dp[(k,0)] = res1\n",
    "                    dp[(k,1)] = res2\n",
    "                    m1 = max(m1, res1, res2 )\n",
    "        return m1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        # 上面的思路两层循环还是超时了，题解给的是定义状态是以j为结尾，删除一次和删除0次的子数组最大和\n",
    "        # 这个删除0次就很骚，可以直接把之前的状态都涵盖了\n",
    "        dp = {}\n",
    "        dp[(0,0)] = arr[0]\n",
    "        max_n = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            dp[(i,0)] = max(dp[(i-1,0)], 0) + arr[i] #如果删除0次，要么就是把之前的都加起来，要么就是还是自己，就问你骚不骚\n",
    "            if i == 1:\n",
    "                dp[(i,1)] = max(arr[0], arr[1])\n",
    "            else:\n",
    "                dp[(i,1)] = max(dp[(i-1,1)] + arr[i], dp[(i-1,0)])\n",
    "            if max_n < dp[(i,0)]:\n",
    "                max_n = dp[(i,0)]\n",
    "            if max_n < dp[(i,1)]:\n",
    "                max_n = dp[(i,1)]\n",
    "        # print(dp)\n",
    "        return max_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j): # 以arr[i]作为右端点 不删/删一次 的最大子数组和\n",
    "            if i < 0: return -inf\n",
    "            x = arr[i]\n",
    "            if j == 0: # 不删\n",
    "                return max(dfs(i - 1, 0) + x, x) # x左边选和不选\n",
    "            else: # 删一次\n",
    "                return max(dfs(i - 1, 0), dfs(i - 1, 1) + x) # 删x 不删x\n",
    "        ans = max(max(dfs(i, 0), dfs(i, 1)) for i in range(n))\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        if len(arr)==0:\n",
    "            return 0\n",
    "        if len(arr)==1:\n",
    "            return arr[0]\n",
    "        if len(arr)==2:\n",
    "            return max([arr[0], arr[1], arr[0]+arr[1]])\n",
    "        \n",
    "        self.f_cache = {}\n",
    "        self.f_min_cache = {}\n",
    "        self.a = arr\n",
    "        return max([\n",
    "            self.f(i, b)                    \\\n",
    "                for i in range(1, len(arr)) \\\n",
    "                    for b in [True, False]  \\\n",
    "        ])\n",
    "    \n",
    "    def f(self, x: int, b: bool):\n",
    "        assert x >= 0\n",
    "        assert not (x == 0 and b)\n",
    "\n",
    "        if (x, b) in self.f_cache.keys():\n",
    "            return self.f_cache[(x, b)]\n",
    "\n",
    "        if x == 0 and not b: # 初始条件f(0, false) = a[0]\n",
    "            result = self.a[0]\n",
    "        elif x == 1 and b: # 初始条件f(1, true) = max(a[0], a[1])\n",
    "            result = max(self.a[0], self.a[1])\n",
    "        else:\n",
    "            if b: # f(x, true)\n",
    "                result = max(\n",
    "                    self.f(x-1, True) + self.a[x], \n",
    "                    self.f(x-1, False) + self.a[x] - min(self.f_min(x-1), self.a[x])\n",
    "                )\n",
    "            else: # f(x, false)\n",
    "                result = self.a[x]                 \\\n",
    "                         if self.f(x-1, False) < 0 \\\n",
    "                         else                      \\\n",
    "                         (self.f(x-1, False) + self.a[x])\n",
    "\n",
    "        self.f_cache[(x, b)] = result\n",
    "        return self.f_cache[(x, b)]\n",
    "    \n",
    "    def f_min(self, x):\n",
    "        assert x >= 0\n",
    "        if x in self.f_min_cache.keys():\n",
    "            return self.f_min_cache[x]\n",
    "        \n",
    "        if x == 0: # 边界条件\n",
    "            result = self.a[0]\n",
    "        elif self.f(x-1, False) < 0:\n",
    "            result = self.a[x]\n",
    "        else:\n",
    "            result = min(self.f_min(x-1), self.a[x])\n",
    "        \n",
    "        self.f_min_cache[x] = result\n",
    "        return self.f_min_cache[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        if len(arr)==0:\n",
    "            return 0\n",
    "        if len(arr)==1:\n",
    "            return arr[0]\n",
    "        if len(arr)==2:\n",
    "            return max([arr[0], arr[1], arr[0]+arr[1]])\n",
    "        \n",
    "        self.f_cache = {}\n",
    "        self.f_min_cache = {}\n",
    "        self.a = arr\n",
    "        return max([\n",
    "            self.f(i, b) \\\n",
    "                for i in range(1, len(arr)) \\\n",
    "                    for b in [True, False] \\\n",
    "        ])\n",
    "    \n",
    "    def f(self, x: int, b: bool):\n",
    "        assert x >= 0\n",
    "        assert not (x == 0 and b)\n",
    "\n",
    "        if (x, b) in self.f_cache.keys():\n",
    "            return self.f_cache[(x, b)]\n",
    "\n",
    "        if x == 0 and not b: # 初始条件f(0, false) = a[0]\n",
    "            result = self.a[0]\n",
    "        elif x == 1 and b: # 初始条件f(1, true) = max(a[0], a[1])\n",
    "            result = max(self.a[0], self.a[1])\n",
    "        else:\n",
    "            if b: # f(x, true)\n",
    "                result = max(\n",
    "                    self.f(x-1, True) + self.a[x], \n",
    "                    self.f(x-1, False) + self.a[x] - min(self.f_min(x-1), self.a[x])\n",
    "                )\n",
    "            else: # f(x, false)\n",
    "                result = self.a[x] \\\n",
    "                         if self.f(x-1, False) < 0 \\\n",
    "                         else \\\n",
    "                         (self.f(x-1, False) + self.a[x])\n",
    "\n",
    "        self.f_cache[(x, b)] = result\n",
    "        return self.f_cache[(x, b)]\n",
    "    \n",
    "    def f_min(self, x):\n",
    "        assert x >= 0\n",
    "        if x in self.f_min_cache.keys():\n",
    "            return self.f_min_cache[x]\n",
    "        \n",
    "        if x == 0: # 边界条件\n",
    "            result = self.a[0]\n",
    "        elif self.f(x-1, False) < 0:\n",
    "            result = self.a[x]\n",
    "        else:\n",
    "            result = min(self.f_min(x-1), self.a[x])\n",
    "        \n",
    "        self.f_min_cache[x] = result\n",
    "        return self.f_min_cache[x]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        if len(arr)==0:\n",
    "            return 0\n",
    "        if len(arr)==1:\n",
    "            return arr[0]\n",
    "        if len(arr)==2:\n",
    "            return max([arr[0], arr[1], arr[0]+arr[1]])\n",
    "        \n",
    "        self.f_cache = {}\n",
    "        self.f_min_cache = {}\n",
    "        self.a = arr\n",
    "        return max([self.f(i, True) for i in range(1, len(arr))] + [self.f(i, False) for i in range(0, len(arr))])\n",
    "    \n",
    "    def f(self, x: int, b: bool):\n",
    "        assert x >= 0\n",
    "        assert not (x == 0 and b)\n",
    "        if (x, b) in self.f_cache.keys():\n",
    "            return self.f_cache[(x, b)]\n",
    "\n",
    "        if x == 0 and not b: # f(0, false) = a[0]\n",
    "            result = self.a[0]\n",
    "        elif x == 1 and b: # f(1, true) = max(a[0], a[1])\n",
    "            result = max(self.a[0], self.a[1])\n",
    "        else:\n",
    "            if b: # f(x, true) = max(f(x-1, true) + a[x], f(x-1, false) + a[x] - min(f_min(x-1), a[x]))\n",
    "                result = max(self.f(x-1, True) + self.a[x], self.f(x-1, False) + self.a[x] - min(self.f_min(x-1), self.a[x]))\n",
    "            else: # f(x, false)\n",
    "                result = self.a[x] if self.f(x-1, False) < 0 else (self.f(x-1, False) + self.a[x])\n",
    "\n",
    "        self.f_cache[(x, b)] = result\n",
    "        return self.f_cache[(x, b)]\n",
    "    \n",
    "    def f_min(self, x):\n",
    "        if x in self.f_min_cache.keys():\n",
    "            return self.f_min_cache[x]\n",
    "        \n",
    "        if x == 0:\n",
    "            result = self.a[0]\n",
    "        elif self.f(x-1, False) < 0:\n",
    "            result = self.a[x]\n",
    "        else:\n",
    "            result = min(self.f_min(x-1), self.a[x])\n",
    "        \n",
    "        self.f_min_cache[x] = result\n",
    "        return self.f_min_cache[x]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        \n",
    "        @cache\n",
    "        def dp(i , j):\n",
    "            if i == 0:\n",
    "                return arr[i]\n",
    "            if j == 0:\n",
    "                return max(dp(i - 1, 0)+ arr[i], arr[i])\n",
    "            else:\n",
    "                return max(dp(i -1, 1) + arr[i], dp(i-1, 0))\n",
    "        ans = float('-inf')\n",
    "        return max([dp(x, y) for x in range(len(arr)) for y in [0,1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumSum(self, arr: List[int]) -> int:\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            if i < 0: return -inf\n",
    "            if j == 0: return max(dfs(i - 1, 0), 0) + arr[i]\n",
    "            return max(dfs(i - 1, 1) + arr[i], dfs(i - 1, 0))\n",
    "        return max(max(dfs(i, 0), dfs(i, 1)) for i in range(len(arr)))"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
